1. Field of the Invention
The present invention relates to radix-r FFTs (Fast Fourier Transforms), and more particularly to a method and an apparatus for assigning data. samples to memory when computing a radix-r FFT.
2. Background of the Invention
Generally, the performance of computer systems is strongly related to memory access speeds. In particular, the present calculation of FFT algorithms requires, intensive memory access and storage operations.
The FFT is a class of algorithms widely used in the field of digital signal processing that break down complex signals into elementary components. The FFT is a discrete fourier transform (DFT) algorithm, which reduces the number of computations needed for N points from 2N2 to 2NlgN, where lg is the base-2.
Radix-r, N-point FFTs can be described by SDF (synchronous data flow) graphs consisting of vertices performing butterfly operations and arcs denoting data transfers between them. A butterfly operation is the smallest constituent part of a FFT and represents a cross multiplication incorporating multiplication, sum and difference operations. The name is derived from the shape of the signal flow diagram. For a radix-2 FFT, the smallest transform or butterfly operation (basic computational unit) used is the 2-point DFT. Each FFT vertex consumes a different set of data and thus, in data processing applications in a computer, accesses a different set of memory locations.
In state of the art FFT computation systems, successive memory accesses to the same memory bank may occur, which will impose the execution of wait states as part of the butterfly operations. An alternative for avoiding such successive accesses is to provide additional memory for temporary storage. This leads to higher costs or the performance of such systems decreases.
It is therefore desirable to minimize or eliminate wait states and to minimize the total memory required when computing a radix-r FFT.
The present invention provides a method and apparatus for assigning data samples to memory when computing a radix-r FFT. This method includes the steps of incrementing a memory bank counter if the fractional part of a data sample divided by a region difference of a butterfly stage equals zero, assigning the data sample to a memory bank indicated by the memory bank counter, executing the first step if the total number of data samples is not reached by a region difference counter counting a region difference change of a butterfly stage, and executing the last step until the total number of data samples is reached by a data sample counter.
The present invention also provides an apparatus for assigning data samples to memory when computing a radix-r FFT, comprising a plurality of memory banks for storing the data samples, a memory bank counter indicating the memory banks, a data sample counter for counting an increment of the data samples, a region difference counter for counting a region difference change of a butterfly stage, a computer program having the current values of the data sample counter and the region difference counter as input values for determining whether the fractional part of the current data sample index divided by the current region difference value equals zero, and a multiplexer for multiplexing the current data sample to an assigned memory bank if the fractional part is not equal zero.
Generally, the present invention minimizes memory and wait states required to implement a FFT in a computer system, while still allowing maximum throughput (single cycle) through the vertices or a butterfly operation. Moreover, the present invention optimizes the trade-off of memory size versus FFT performance.